package com.zcmyth;

import static org.junit.Assert.assertEquals;

import java.util.List;

import org.junit.Before;
import org.junit.Test;

import com.google.common.collect.ImmutableList;
import com.google.common.collect.Lists;
import com.zcmyth.tree.BinaryTree;
import com.zcmyth.tree.TreeInOrderIterator;

public class TreeOrderIteratorTest {

  private BinaryTree<Integer> tree;

  //      o(0)
  //    o(1) o(2)
  // o(3) o(4)

  @Before
  public void buildTree() {
    BinaryTree.Node<Integer> root = new BinaryTree.Node<Integer>(0);
    BinaryTree.Node<Integer> left = new BinaryTree.Node<Integer>(1);
    BinaryTree.Node<Integer> right = new BinaryTree.Node<Integer>(2);
    root.setLeft(left);
    root.setRight(right);
    BinaryTree.Node<Integer> ll = new BinaryTree.Node<Integer>(3);
    BinaryTree.Node<Integer> rr = new BinaryTree.Node<Integer>(4);
    left.setLeft(ll);
    left.setRight(rr);
    tree = new BinaryTree<Integer>(root);
  }

  @Test
  public void inOrder() {
    TreeInOrderIterator<Integer> iterator = new TreeInOrderIterator<Integer>(tree);
    List<Integer> list = Lists.newArrayList(iterator);
    assertEquals(ImmutableList.of(3, 1, 4, 0, 2), list);
  }
}
